/*
https://leetcode-cn.com/problems/wiggle-subsequence/solution/bai-dong-xu-lie-by-leetcode-solution-yh2m/
 */
public class Solution376 {
    public int wiggleMaxLength(int[] nums) {
        int[] up=new int[nums.length];
        int[] down=new int[nums.length];
        up[0]=down[0]=1;
        for (int i=1;i<nums.length;i++){
            up[i]=nums[i]>nums[i-1]?Math.max(up[i-1],down[i-1]+1):up[i-1];
            down[i]=nums[i]<nums[i-1]?Math.max(down[i-1],up[i-1]+1):down[i-1];
        }
        return Math.max(up[nums.length-1],down[nums.length-1]);
    }

    public static void main(String[] args) {
        System.out.println(new Solution376().wiggleMaxLength(new int[]{1,17,5,10,13,15,10,5,16,8}));
    }
}
